This invention relates to multipoint communications systems which employ handshaking, random access and collision detection techniques, and more particularly to such systems where information must be received from a plurality of responding terminals. Specifically, the invention can be applied to a supermarket checkout system designed to reduce checkout time at the point of sale where, typically, many items are purchased by a customer.
Other possible applications of the invention include, for example, retail sales in general; delivery control; inventory control; security check of objects or beings occupying, or entering or leaving a defined area; automatic toll collection or monitoring of moving vehicles; telemetry; and network data communications in general.
Several approaches have been taken to implement communications systems which receive information from multiple terminals. In general, these can be referred to as transponder implementations, and communications protocols, including the Aloha technique, carrier sense multiple access with collision detection, and time division multiple access.
An advantage to using transponders is their relative simplicity. Transponders receive electromagnetic energy at a specific frequency from an interrogator and transmit back a signal which may be a continuous tone or an information-containing message such as an ID code. Typically, transponders do not permit sophisticated two-way communications, using a protocol, to enable the interrogator to coordinate or separate the responses from multiple transponders. Because of this, in applications where two or more transponders are identical and are located closely together, it may not be possible for the interrogator to determine the number of communicating transponders or to separate out communications from multiple transponders.
The Aloha technique provides one way in which multiple stations can share a communication channel over which only one transmission can be received at a time. Using the Aloha technique, when a station has information to transmit, it simply transmits it, without first being signaled that the communication channel is available. Because it is possible for more than one station to transmit at the same time, several transmissions may overlap or "collide," as it is called in the art. When a collision occurs, the network controller can either signal the station to retransmit its data or the network controller can simply drop the transmission and wait for the station to resend it. The principal disadvantage of the Aloha technique is that it can only be employed effectively when the likelihood of collision is very low, such as when the communication channel is idle most of the time.
One specific example of a system using the Aloha technique is found in U.S. Pat. No. 4,352,183 to Davis et al. In an effort to overcome problems in the most basic form of the Aloha technique, the system described in U.S. Pat. No. 4,352,183 employs a protocol for determining when a particular transmitter is allowed to transmit. A controlling transmitter first broadcasts an initial command signal to all the transmitters to indicate that a communication channel has become available. Each transmitter having data to send transmits a request for information transmission message to the controlling transmitter in a randomly chosen one of a predetermined number of timeslots following receipt of the initial command signal. If no collisions are detected, the controlling transmitter responds with an acknowledgment signal addressed to the particular transmitter that sent a request for information transmission message, thereby permitting that transmitter to send a data-containing message to the controlling transmitter. A disadvantage of this system is that the controlling transmitter must periodically issue command signals to indicate when a communication channel becomes available. Another disadvantage is that the controlling transmitter must issue a command signal addressed specifically to the requesting transmitter before that transmitter is permitted to send a data-containing signal.
The carrier sense multiple access with collision detection protocol provides a way of reducing collisions between transmissions in more heavily utilized networks. This protocol is well-known in the art and has evolved into an industry standard: IEEE Standard 8802.3-1992, Information Technology--Local and Metropolitan Area Networks--Part 3: Carrier Sense Multiple Access with Collision Detection (CSMA/CD) Access Method and Physical Layer. Specifications, Institute for Electrical and Electronics Engineers, Piscataway, N.J. 08855-1331.
Under this protocol, multiple stations can respond to the same interrogator, hence the name multiple access. However, before attempting to transmit, each station monitors the channel to determine if another station is communicating (i.e. the station senses the presence of a carrier frequency), hence the name, carrier sense, and if so, waits for the other station to finish transmission before attempting to transmit information. The interrogator responds according to whether or not two or more stations attempt to transmit simultaneously (i.e. collision detection). A disadvantage of this protocol when applied to systems where a single device interrogates a large number of stations simultaneously is that collisions are frequent and throughput low because several stations attempt to transmit whenever the channel is found to be available.
Another protocol, time division multiple access, has been used in multipoint communication systems. Under this approach, each station is assigned, based on its own unique identifying characteristics, one of a predetermined number of timeslots in which to transmit. To complete longer transmissions, each station communicates during its assigned timeslot over multiple cycles. A problem with this approach is that the interrogator must be able to distinguish between the responding stations prior to requesting data from them in order to assign an individual timeslot to each.
European Patent Application EP 0 409 016 A2 describes a system for locating predetermined labeled objects. An interrogator has a narrow beamwidth antenna for transmitting an energizing signal at a predetermined first frequency. A transponder incorporated in the label on each of the labeled objects receives the energizing signal and transmits a return signal at a predetermined second frequency. The energizing signal incorporates a predetermined transponder identification code. If the predetermined transponder identification code matches the identification code stored in the transponder, the transponder transmits a return signal.
The system of EP 0 409 016 A2 may also be used to locate objects within a predetermined category of a plurality of objects. In this mode, the interrogator transmits a predetermined category code to all of the transponders, and waits for receipt of signals containing an identification code from each of the transponders which have a stored category code which matches the predetermined category code that was transmitted. To assist in avoiding collisions between their signals when responding, each transponder waits after energization for a predetermined delay period before responding, the length of the delay period being determined from a code stored in the transponder's memory.
A disadvantage of the system of EP 0 409 016 A2, where used with a large number of objects to be identified, is the need for the interrogator to be cognizant of the transponder identification codes a priori; that is, in advance of any communications made by the transponder. Another disadvantage of the system, where used with a large number of objects, is the need to store a predetermined time delay code in each transponder which is distinct from all the other time delay codes of transponders belonging to the same category. In general, this characteristic can be expected to increase the total time required to locate a subset of the objects in a category because many of the possible time delay codes of the category will be unused.
European Patent Application EP 0 494 114 A2 describes a supermarket checkout system having an interrogator and a plurality of transponders, each transponder being attached to an individual object to be identified. In that system, an interrogation signal is first transmitted by a central interrogator to all of the transponders. On receipt of the interrogation signal, each transponder transmits a response identifying the particular transponder. Without waiting for further communication from the interrogator and at intervals which are determined randomly or pseudo-randomly by circuitry within each transponder, each transponder repeats its identifying response two more times in succession to increase the probability of successful reception of its response by the interrogator.
That system further describes use of an interrogation signal which can be modulated intermittently with the identification code of a particular transponder, or with a code identifying a category of transponders, so as to cause to respond only the particular transponder or category of transponders which have the same identification code or category code stored in the particular transponder's memory. Identification codes are transmitted and received digitally with error correction and detection bits to improve the chances that the interrogator determine when it has received a response correctly from a transponder.
Under the system of EP 0 494 114 A2, if the interrogator receives a response from a transponder correctly, the interrogator signals the same to the transponder by momentarily interrupting the interrogation signal. The transponder is adapted to sense the interruption of the interrogation signal and stops transmitting its response under such conditions.
A problem of the system of EP 0 494 114 A2, where used with multiple objects to be identified, is that the response signals can be expected to always collide during the first transmission because they are timed to be sent by all transponders immediately on receipt of the interrogation signal. Thus, under this system the response signals during the first transmission can generally be expected to be received in error. Unnecessary delay and possibly undetected errors may result from a system the operation of which is conditioned on detecting errors in the responses of multiple transponders which are all intended to be transmitted simultaneously. Another problem of this system, where used with large numbers of objects to be identified, lies in the lack of an affirmatively granted transmission time for each transponder to respond. Although each transponder is adapted to repeat its response signal, the system is not designed to ensure that each transponder has a time to transmit which is distinct from the times that all other transponders are transmitting, as might be the case if the interrogator were to affirmatively signal the individual transponder that a transmission time had been granted.